package com.nowcoder.Offer.Array;

import org.junit.Test;

/**
 * 找出出现次数超过一半的数字
 */
public class FindTopCountNum {

    public int MoreThanHalfNum_Solution(int [] array) {
        int time = 1;
        int cur = array[0];
        for(int i=0; i<array.length; i++){
            if(array[i] == cur){
                time++;
            }else{
                if(time>1) time--;
                else{
                    cur = array[i];
                    time = 1;
                }
            }
        }

        time = 0;
        for(int e : array){
            if(e == cur){
                time++;
            }
        }

        return time > array.length >> 1 ? cur : 0;
    }

    @Test
    public void test(){
        int[] arr = {1,2,3,2,2,2,5,5,4,2};
        System.out.println(MoreThanHalfNum_Solution(arr));
    }
}
